{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import sklearn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 集成学习的概念与基于树算法的发展史\n",
    "\n",
    "下图截止到2014年，后来的LightGBM对XGBoost又进行了一些优化\n",
    "![image.png](基于树算法的发展史.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从图中可以看出，决策树以后的几种算法都是结合了多个学习器来完成学习任务，这就是**集成学习（ensemble learning）**，又称作多分类器系统（multi-classifier system）、基于委员会的学习（committee-based learning）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据集成学习的结构，可分为：\n",
    "- 同质（homogeneous）：集成的学习器都一样的，每个学习器叫做基学习器，相应的学习算法叫做基学习算法。\n",
    "- 异质（heterogeneous）：包含不同类型的学习器，每个学习器叫做组件学习器。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 准确性和多样性\n",
    "在集成学习中，有两个重要概念：**准确性**和**多样性**。从下图中可以看出，好的集成学习中个体学习器应具备较高的准确性和多样性。\n",
    "![集成个体应该“好而不同”](集成个体应该“好而不同”.png \"集成个体应该“好而不同”\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 集成学习的错误率与个体分类器个数的关系"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以二分类问题为例，谈论个体学习器个数$T$（为便于讨论，设其为奇数）对于集成学习错误率的影响。\n",
    "\n",
    "我们知道，如果有半数个体分类器分类正确，则集成分类就正确（反之，不足半数，则继承分类就错误）。假设各个体分类器错误率相互独立（实际不可能）时，一次集成学习中有$k$个分类器分类错误的概率为（可以用n重伯努利概型解决）：\n",
    "$$\\binom{T}{k}(1-\\epsilon)^k\\epsilon^{T-k}$$，其中，$\\epsilon$是个体分类器的错误率。\n",
    "\n",
    "因此，$k< \\lfloor T/2 \\rfloor$时，集成学习器就是分类错误的。可知集成的错误率为\n",
    "$$P(F(x)≠f(x))=\\sum_{k=0}^{\\lfloor T/2 \\rfloor}\\binom{T}{k}(1-\\epsilon)^k\\epsilon^{T-k}$$，其中，$F(x)$是集成学习的输出，$f(x)$是真实输出函数。\n",
    "\n",
    "基于霍夫丁（Hoeffding）不等式，有\n",
    "$$P(F(x)≠f(x))=\\sum_{k=0}^{\\lfloor T/2 \\rfloor}\\binom{T}{k}(1-\\epsilon)^k\\epsilon^{T-k}≤exp(-\\frac{1}{2}T(1-2\\epsilon)^2)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**可知**：集成的错误率伴随个体继承器$T$的增大而指数级下降，并趋于0。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "个体学习器的“准确性”和“差异性”是一对矛盾的变量，准确性高意味着牺牲多样性，跟据个体学习器的生成方式，集成学习方法可分为两类：\n",
    "- 个体学习器存在强依赖、串行生成的序列化方法：Boosting\n",
    "- 个体学习器不存在强依赖、同时生成的并行化方法：Bagging、随机森林（Random Forest）"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
